package com.zhengb.algorithmdemo.leetcode.statck;

/**
 * 请设计一个栈，除了常规栈支持的pop与push函数以外，还支持min函数，该函数返回栈元素中的最小值。
 * 执行push、pop和min操作的时间复杂度必须为O(1)。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/min-stack-lcci
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author zhengbo
 * @date 2020/3/14
 */
public class MinStack {

    private static class Node {
        /**
         * 节点值
         */
        public int value;

        /**
         * 下一个节点
         */
        public Node next;

        /**
         * 当前节点入栈后栈中所有元素最小值
         * 栈顶元素的minValue为当前栈中所有元素的最小值
         */
        public int minValue;

        public Node(int value, int minValue) {
            this.value = value;
            this.minValue = minValue;
        }
    }

    private Node headNode;

    public MinStack() {
        headNode = null;
    }

    public void push(int x) {

        if (headNode == null) {
            //头结点为空 值和最小值都为x
            headNode = new Node(x, x);
        } else {
            //与栈顶元素比较
            int minValue = Integer.min(x, headNode.minValue);
            //新插入节点minValue为当前栈所有元素最小值
            Node newNode = new Node(x, minValue);
            //更改指针
            newNode.next = headNode;
            headNode = newNode;

        }
    }

    public void pop() {
        Node curNode = headNode;

        headNode = curNode.next;
        //help GC
        curNode = null;
    }

    public int top() {
        return headNode.value;
    }

    public int getMin() {
        return headNode.minValue;
    }

    public static void main(String[] args) {
        MinStack minStack = new MinStack();
        minStack.push(-2);
        minStack.push(0);
        minStack.push(-3);

        System.out.println(minStack.getMin());
        minStack.pop();
        System.out.println(minStack.top());
        System.out.println(minStack.getMin());
    }
}
